/***************************************************
 * @Author: OBKoro1
 * @Create: 2020-04-06
 * @LastEditors: OBKoro1
 * @LastEditTime: 2020-04-06
 * @FilePath: \leetcode-exercise\611-有效三角形的个数\answer.c
 ****************************************************/
/* 解题思路：
* 三角形的任意两边之和大于第三边”，事实上，只要最短的两条边大于第三边就好，剩下的就不用判断了，我的理由如下：既然边长是实数，不妨将这些边排个序。
  假设有索引 i < j < k 使得 nums[i] <= nums[j] <= nums[k] 成立，不妨称它们为“短”、“中”、“长”，显然有：
  在任何情况下，“短 + 长 > 中”成立。
  在任何情况下，“中 + 长 > 短”成立。
  题目的关键是先排序，再二分查找：
  （1）因为以后的边越来越长，这条边以及以后的边都不能和前面的两条边构成三角形；
  （2）因为是第 1 个不满足构成三角形的第三条边，那这个索引和 j 之间的所有数都满足构成三角形，
    得到“一票解”（一系列解的意思），注意边界条件（边界条件一般在草稿纸上举例就很清楚了）
    因此将数组从小到大排序，固定 i,j ,在j+1 ~ size 之间找到第一个不满足条件的k，则j+1 ~ K则是满足条件的解
*/
// 注意qsort函数的使用规则
// 升序排序
int compare(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

// 二分查找到第一个不满足条件的索引
int binSearch(int *nums, int numsSize, int start, int k)
{
    int low = start;
    int high = numsSize - 1;
    int mid;

    // 全部都小于则不需要进行二分查找了
    if (nums[high] < k)
    {
        return high;
    }
    // 全部都大于则不需要二分查找了
    if (nums[low] >= k)
    {
        return (low - 1);
    }

    while (low <= high)
    {
        mid = (high + low) / 2;
        // 找到第一个满足条件的值
        if ((nums[mid] >= k) && (nums[mid - 1]) < k)
        {
            return (mid - 1);
        }
        else if (nums[mid] < k)
        {
            low = mid + 1;
        }
        else /* nums[mid] > 0  and nums[mid - 1] >= k */
        {
            high = mid - 1;
        }
    }
    return high;
}

int triangleNumber(int *nums, int numsSize)
{
    int res = 0;
    int idx;
    int i;
    int j;
    int tmp;
    if (numsSize < 3)
    {
        return res;
    }
    // 升序排序
    qsort(nums, numsSize, sizeof(int), &compare);
    for (i = 0; i < numsSize - 2; i++)
    {
        for (j = i + 1; j < numsSize - 1; j++)
        {
            /* 计算两边之和 num[i] <= num[j] */
            tmp = nums[i] + nums[j];
            /* 二分查找 j+1 到 size之间第一个不满足条件的k */
            idx = binSearch(nums, numsSize, (j + 1), tmp);
            res += (idx - j);
        }
    }
    return res;
}